perm filename T.LST[144,DBL] blob
sn#026388 filedate 1973-02-26 generic text, type T, neo UTF8
MIXAL - MIX Assembly Language
26-FEB-1973 16:40
0000 + 0000000024 BLANKS ORIG *+24 ;These locs. should always be blank.
0024 + 0000000000 N CON 0 ;The number of nodes
0025 + 0000000049 TPL ORIG *+24 ;The desired total path length
0049 + 0000000000 LOG CON 0 ;A sequential linear list, whose i th element
* is Floor(log(i)), where log ≡ (log to base 2).
0050 + 0000000550 ORIG *+500 ;I have assumed that n will never be > 500.
0550 + 0000000000 S CON 0 ;A sequential linear list whose i th element
* is the sum of elements 1 to i of LOG.
0551 + 0000001051 ORIG *+500
1051 + 0000000000 TREE CON 0 ;An internal representation of the final tree.
1052 + 0000001552 ORIG *+500
+ 0000003500 ZEROS EQU 3500 ;An area which remains as zeros.
+ 0000000009 VISIT EQU 1:1 ;The field spec. indicating whether or not wehave visited this no1552 + 0000002352 BUFFER ORIG *+800 ;This should be ample to hold a finaltree traversal encoding.
2352 + 0000000000 DIFF CON 0 ;Holds the difference between the pure balanced+
* tail tree path length, and the desired TPL.
2353 + 0000000000 XOLD CON 0 ;Holds the previous path length, in case we went too far.
2354 + 0000000000 K CON 0 ;Holds the number of nodes in the balanced part oftree.
2355 + 00 00 00 15 00 TITLE ALF N
2356 + 00 00 23 17 13 ALF TPL
2357 + 00 00 00 00 00 ALF
2358 + 00 00 00 00 00 ALF
2359 + 00 00 00 00 00 ALF
2360 + 04 16 24 07 00 ALF Doug
2361 + 13 05 15 01 23 ALF Lenat
2362 + 00 00 00 00 00 ALF
2363 + 03 22 00 31 34 ALF CS 14
2364 + 34 01 00 00 17 ALF 4A P
2365 + 19 16 02 13 05 ALF roble
2366 + 14 00 00 34 00 ALF m 4
2367 + 00 00 00 00 00 ALF
2368 + 23 16 23 01 13 ALF Total
2369 + 00 17 01 23 08 ALF Path
2370 + 00 13 05 15 07 ALF Leng
2371 + 23 08 00 09 15 ALF th in
2372 + 00 02 09 15 01 ALF Bina
2373 + 19 28 00 23 19 ALF ry Tr
2374 + 05 05 22 00 00 ALF ees
2375 + 0000002380 ORIG *+5
+ 0000000036 RSON EQU 4:4 ;Field in a TREE node pointing to right son.
+ 0000000045 LSON EQU 5:5 ;Field specification pointing to the left son.
* note that this restricts n to be under 65; a trivial modification
* will allow n to range up to 500.If n is requested over 2000, a
* total revision of the program would be necessary.
+ 0000000037 SONS EQU 4:5 ;Field which is blank iff the node is a leaf.
+ 0000000027 FATHER EQU 3:3 ;Field spec. pointing to the node's parent.
+ 0000000036 FIELD EQU 4:4 ;Field spec. for the field byte of a MIX instruction.
+ 0000000042 LPAREN EQU 42
+ 0000000043 RPAREN EQU 43
+ 0000000046 STAR EQU 46
+ 0000000016 READER EQU 16
+ 0000000018 PRINTER EQU 18
*
*
2380 + 0000 00 18 37 CONTINU OUT BLANKS(PRINTER)
2381 + 0000 00 18 37 OUT BLANKS(PRINTER)
2382 + 0024 00 16 36 START IN N(READER) ;Read n. We are permitted the inefficiency of
2383 + 2383 00 16 34 JBUS *(READER) ;JBUS instructions. See Knuth and
* my earlier programs for examples
* of more efficient I/O.
2384 + 0024 00 05 15 LDX N
2385 + 2387 00 04 47 JXNZ *+2 ;Are we finished the final problem in the run??
2386 + 0000 00 02 05 HLT ; yes; so we halt.
2387 + 2355 00 18 37 OUT TITLE(PRINTER) ; Here we
* write out a title line.
2388 + 0024 00 18 37 OUT N(PRINTER) ;We write n and tpl
2389 + 2389 00 18 34 JBUS *(PRINTER) ; while they are still in char. form.
2390 + 0000 00 02 48 ENTA 0
2391 + 0000 00 00 05 NUM
2392 + 0024 00 05 24 STA N ; re-store the numeric value of n.
2393 + 0025 00 05 15 LDX TPL ;Convert TPL from char. code to numeric.
2394 + 0000 00 02 48 ENTA 0
2395 + 0000 00 00 05 NUM
2396 + 0025 00 05 24 STA TPL
2397 + 1051 00 02 49 ENT1 TREE
2398 + 0024 00 05 10 LD2 N
2399 + 2400 00 36 26 ST2 *+1(FIELD)
2400 + 3500 00 01 07 MOVE ZEROS ;WARNING: INSTRUCTION MODIFICATION HERE.
*
*
* The following loop sets up the first n entries in LOG and in S:
*
2401 + 0000 00 02 49 ENT1 0 ;rI1 holds the exponent of the current power of 2.
2402 + 0000 00 02 50 ENT2 0 ;rI2 holds the sum of all previous terms.
2403 + 0001 00 02 51 ENT3 1 ;rI3 holds 2 to the current power( 2 ↑ <rI1> ).
2404 + 0000 00 02 52 ENT4 0 ;rI4 stops us when n terms have been computed.
2405 + 0001 00 02 48 ENTA 1 ;rA tells us when to increase the terms of LOG.
*
2406 ↓ - 0001 00 00 39 JMP LOOP1 ;A standard programming trick, saving n-1 tyme units.
2407 + 0000 03 00 51 SKIP1 INC3 0,3 ;Double rI3; i.e, increaase its log by 1.
2408 + 0000 03 02 48 ENTA 0,3 ;rA tells us when to increase the terms of LOG.
2409 + 0001 00 00 49 INC1 1
2410 ← + 0000 01 00 50 LOOP1 INC2 0,1
2411 + 0001 00 00 52 INC4 1
2412 + 0550 04 05 26 ST2 S,4
2413 + 0049 04 05 25 ST1 LOG,4
2414 + 0001 00 01 48 DECA 1
2415 + 2410 00 02 40 JAP LOOP1
2416 + 0024 00 05 60 CMP4 N
2417 + 2407 00 09 39 JLE SKIP1
*
*
*
*
* This loop is the "guts" of the program: we determine how many nodes
* are in the balanced section, and how many are in the tail.
*
2418 + 0000 00 02 51 ENT3 0 ;rI3 holds the L*(L+1)/2 term.
2419 + 0024 00 05 13 LD5 N ;rI5 holds K, the number of nodes in the balanced part.
2420 - 0001 00 02 54 ENT6 -1 ;rI6 holds L, the number of nodes in the tail.
2421 + 0000 06 01 53 DEC5 0,6 ;K must always remain equal to N - L.
2422 + 0001 00 00 54 LOOP2 INC6 1
2423 + 0001 00 01 53 DEC5 1
2424 + 0000 06 00 51 INC3 0,6 ;Update this term.
2425 + 2353 00 05 24 STA XOLD
2426 + 0000 06 02 48 ENTA 0,6 ;Get the L * Floor(log(k)) term.
2427 + 0049 05 05 03 MUL LOG,5
2428 + 0005 00 02 06 SLAX 5
2429 + 0000 03 00 48 INCA 0,3 ;The accumulator now contains the sum of terms 1,2.
2430 + 0550 05 05 01 ADD S,5 ;We add in the sum of LOGs from 1 to K: the final term.
2431 + 0025 00 05 56 CMPA TPL ;See if we have gone far enough....
2432 + 2422 00 04 39 JL LOOP2 ; we haven't; go back and try again.
* WE HAVE SUCCEEDED !!!
*
2433 + 0025 00 05 08 LDA TPL
2434 + 2353 00 05 02 SUB XOLD
2435 + 2352 00 05 24 STA DIFF
2436 + 0001 00 00 53 INC5 1
2437 + 0001 00 01 54 DEC6 1
*
*
*
* Here we set up the tree; only one node will have to be moved.
*
* LOOP3 sets up the balanced section of the tree
*
2438 + 0000 00 02 50 ENT2 0 ;rI2 now keeps track of the father node.
2439 + 2354 00 05 29 ST5 K
2440 + 0001 00 00 50 LOOP3 INC2 1
2441 + 0000 02 02 49 ENT1 0,2 ;rI1 holds the location of the son(s). In general,
2442 + 0000 02 00 49 INC1 0,2 ; node m will have as children nodes 2m and 2m+1.
2443 + 1051 02 45 25 ST1 TREE,2(LSON)
2444 + 1051 01 27 26 ST2 TREE,1(FATHER)
2445 + 1051 01 37 33 STZ TREE,1(SONS)
2446 + 2354 00 05 57 CMP1 K
2447 ↓ - 0001 00 07 39 JGE SETREE2
2448 + 0001 00 00 49 INC1 1
2449 + 1051 02 36 25 ST1 TREE,2(RSON)
2450 + 1051 01 27 26 ST2 TREE,1(FATHER)
2451 + 1051 01 37 33 STZ TREE,1(SONS)
2452 + 2354 00 05 57 CMP1 K
2453 + 2440 00 04 39 JL LOOP3
*
* SETREE2 sets up section 2 of the tree: the tail part
*
2454 ← + 1052 01 27 25 SETREE2 ST1 TREE+1,1(FATHER) ;Now rI1 is the father, and rI1+1 is son.
2455 + 0001 00 00 49 INC1 1
2456 + 1050 01 45 25 ST1 TREE-1,1(LSON)
2457 + 0024 00 05 57 CMP1 N
2458 + 2454 00 04 39 JL SETREE2
*
*
*
* LOOP4 locates a leaf in the balanced section.
*
2459 + 0000 00 02 49 ENT1 0
2460 + 0001 00 00 49 LOOP4 INC1 1
2461 + 1051 01 37 08 LDA TREE,1(SONS)
2462 + 2460 00 04 40 JANZ LOOP4
*
* Now we have located a leaf. We shall now cut it off the tree:
*
2463 + 1051 01 27 10 LD2 TREE,1(FATHER)
2464 + 0045 00 02 51 ENT3 LSON
2465 + 1051 02 45 57 CMP1 TREE,2(LSON)
2466 + 2468 00 05 39 JE *+2
2467 + 0036 00 02 51 ENT3 RSON ;rI3 now contains the field spec. pointing to leaf.
2468 + 2469 00 36 27 ST3 *+1(FIELD); BE CAREFUL: WE ARE MODIFYING THE NEXT INSTRUCTION!!
2469 + 1051 02 05 33 STZ TREE,2
*
* Now we see how deep our leaf used to be:
*
2470 + 0000 00 02 51 ENT3 0
2471 + 1051 02 27 10 LOOP5 LD2 TREE,2(FATHER)
2472 + 0001 00 00 51 INC3 1
2473 + 2471 00 02 42 J2P LOOP5
*
* rI3 now contains that quantity. Now we examine how far we must move it.
*
2474 + 0049 05 05 08 LDA LOG,5
2475 + 0001 06 00 48 INCA 1,6 ; rA now contains the depth of the deepest node, node n.
2476 + 0000 03 01 48 DECA 0,3 ; Subtract the leaf's old depth.
2477 + 2352 00 05 02 SUB DIFF ; Subtract how many levels down the leaf must be moved.
*
* The accumulator now contains the number of moves upward from the tip of
* the tail of the tree we must make before we insert the leaf back in.
* we move a pointe upward from the final node this number of levels:
*
2478 + 0024 00 05 10 LD2 N
2479 + 1051 02 27 10 LOOP6 LD2 TREE,2(FATHER)
2480 + 0001 00 01 48 DECA 1
2481 + 2479 00 02 40 JAP LOOP6
*
* Insert the leaf back into the tree at the proper position:
*
2482 + 1051 01 27 26 ST2 TREE,1(FATHER)
2483 + 1051 02 36 25 ST1 TREE,2(RSON)
*
* Print out the final tree in post order:
*
2484 + 0046 00 02 49 ENT1 STAR
2485 + 0042 00 02 48 ENTA LPAREN
2486 + 0043 00 02 55 ENTX RPAREN
2487 + 0000 00 02 52 ENT4 0 ;rI4 holds the present position to be filled in the
* output buffer.
2488 + 0001 00 02 53 ENT5 1 ;rI5 points to the current position in
* the traversal of the tree.
2489 ↓ - 0001 00 00 39 JMP LOOP7
2490 + 0001 00 01 52 L7AA DEC4 1
2491 + 1051 05 27 13 LOOP7A LD5 TREE,5(FATHER)
2492 ↓ - 0001 00 01 45 J5Z LOOP8
2493 + 1552 04 05 31 STX BUFFER,4
2494 + 0001 00 00 52 INC4 1
2495 ← + 1051 05 09 11 LOOP7 LD3 TREE,5(VISIT) ;If we have visited this node before, move up one
* level, to its father. Else we shall try to go left.
2496 + 2491 00 02 43 J3P LOOP7A
2497 + 0000 05 02 50 GOLEFT ENT2 0,5
2498 + 1051 05 45 13 LD5 TREE,5(LSON)
2499 + 1552 04 05 24 STA BUFFER,4
2500 + 0001 00 00 52 INC4 1
2501 + 1051 05 09 11 LD3 TREE,5(VISIT)
2502 ↓ - 0001 00 02 43 J3P STAY ;If we have visited the left branch already, visit the node itsel2503 + 2497 00 02 45 J5P GOLEFT ;If we can continue down the left subtree, do so.
2504 ← + 1051 02 09 24 STAY STA TREE,2(VISIT) ;Visit this node. Mark it as such.
2505 + 1551 04 05 25 ST1 BUFFER-1,4
2506 + 0000 02 02 53 ENT5 0,2
2507 + 0000 05 02 50 GORIGHT ENT2 0,5 ;Here we attempt to go right (move to right son).
2508 + 1051 05 36 13 LD5 TREE,5(RSON)
2509 + 1552 04 05 24 STA BUFFER,4
2510 + 0001 00 00 52 INC4 1
2511 + 2495 00 02 45 J5P LOOP7
2512 + 1051 02 27 13 LD5 TREE,2(FATHER) ;There is no right son; move upward one level and continue.
2513 + 1551 04 05 31 STX BUFFER-1,4
*
2514 + 2495 00 02 45 J5P LOOP7
2515 + 1551 04 05 33 STZ BUFFER-1,4
*
* Here we do the actual printing of the encoded traversal
*
2516 ← + 0000 00 02 51 LOOP8 ENT3 0
2517 + 1552 03 18 37 LOOP9 OUT BUFFER,3(PRINTER)
2518 + 0024 00 00 51 INC3 24
2519 + 0024 00 01 52 DEC4 24
2520 + 2517 00 03 44 J4NN LOOP9
*
* Go back and read in a new request
*
2521 + 2380 00 00 39 JMP CONTINU ;This differs from START only in the printing out of 2 blank line *
2522 + 000000 2382 END START
SYMBOL TABLE
BLANKS +0
N +24
TPL +25
LOG +49
S +550
TREE +1051
ZEROS +3500
VISIT +9
BUFFER +1552
DIFF +2352
XOLD +2353
K +2354
TITLE +2355
RSON +36
LSON +45
SONS +37
FATHER +27
FIELD +36
LPAREN +42
RPAREN +43
STAR +46
READER +16
PRINTER +18
CONTINU +2380
START +2382
LOOP1 +2410 (2406)
SKIP1 +2407
LOOP2 +2422
LOOP3 +2440
SETREE2 +2454 (2447)
LOOP4 +2460
LOOP5 +2471
LOOP6 +2479
LOOP7 +2495 (2489)
L7AA +2490
LOOP7A +2491
LOOP8 +2516 (2492)
GOLEFT +2497
STAY +2504 (2502)
GORIGHT +2507
LOOP9 +2517